package jzoffer;

/**
 * 判断给的数组是否为某个二叉搜索树的后序遍历
 * @author MaoLin Wang
 * @date 2020/10/10 10:37 上午
 */
public class _33二叉搜索树的后序遍历 {
    public static boolean verifyPostorder(int[] postorder) {
        return digui(postorder,0,postorder.length-1);
    }

    private static boolean digui(int[] postorder, int i, int j) {
        if (i>=j){
            return true;
        }
        int x=i;
        while (postorder[i]<postorder[j]){
            x++;
        }
        int firstMax=x;//第一个大于根节点的节点 ，即右子树最小的节点
        while (postorder[x]>postorder[j]){
            x++;
        }
        return x==j && digui(postorder,i,firstMax-1) && digui(postorder,firstMax,j-1);

    }
}
